//https://leetcode.cn/problems/count-of-smaller-numbers-after-self/

class Solution {
    vector<int> ret;
    vector<int> index;
    int tempnums[500010];
    int tempindex[500010];
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n);
        index.resize(n);

        for (int i = 0; i < n; i++)
        {
            index[i] = i;
        }

        mergesort(nums, 0, n - 1);

        return ret;
    }

    void mergesort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return;

        int mid = (l + r) >> 1;

        mergesort(nums, l, mid);
        mergesort(nums, mid + 1, r);

        int cur1 = l, end1 = mid, cur2 = mid + 1, end2 = r, i = 0;
        while (cur1 <= end1 && cur2 <= end2)
        {
            if (nums[cur1] <= nums[cur2])
            {
                tempnums[i] = nums[cur2];
                tempindex[i++] = index[cur2++];
            }
            else
            {
                ret[index[cur1]] += end2 - cur2 + 1;
                tempnums[i] = nums[cur1];
                tempindex[i++] = index[cur1++];
            }
        }

        while (cur1 <= end1)
        {
            tempnums[i] = nums[cur1];
            tempindex[i++] = index[cur1++];
        }

        while (cur2 <= end2)
        {
            tempnums[i] = nums[cur2];
            tempindex[i++] = index[cur2++];
        }

        for (int j = l; j <= r; j++)
        {
            nums[j] = tempnums[j - l];
            index[j] = tempindex[j - l];
        }
    }
};